Current medium access control mechanisms are based on collision avoidance andcollided packets are discarded. The recent work on ZigZag decoding departs fromthis approach by recovering the original packets from multiple collisions. Inthis paper, we present an algebraic representation of collisions which allowsus to view each collision as a linear combination of the original packets. Thetransmitted, colliding packets may themselves be a coded version of theoriginal packets. We propose a new acknowledgment (ACK) mechanism for collisions based on theidea that if a set of packets collide, the receiver can afford to ACK exactlyone of them and still decode all the packets eventually. We analyticallycompare delay and throughput performance of such collision recovery schemeswith other collision avoidance approaches in the context of a single hopwireless erasure network. In the multiple receiver case, the broadcastconstraint calls for combining collision recovery methods with network codingacross packets at the sender. From the delay perspective, our scheme, withoutany coordination, outperforms not only a ALOHA-type random access mechanisms,but also centralized scheduling. For the case of streaming arrivals, we proposea priority-based ACK mechanism and show that its stability region coincideswith the cut-set bound of the packet erasure network.
展开▼